import java.util.Arrays;

/**
 * 以空间换时间
 * 计数排序适合范围适合对较为集中的数据进行排序，并且范围不大的数据
 * 时间复杂度：O(范围+N)
 * 空间复杂度：O(范围) 99 - 91 = 8 + 1
 */
public class CountSort {
    public static void countSort(int[] array) {
        //1.找到数组中的最大值与最小值  O(N)
        int maxVal = array[0];
        int minVal = array[0];
        for(int i = 1; i < array.length;i++) {
            if(array[i] > maxVal) {
                maxVal = array[i];
            }
            if(array[i] < minVal) {
                minVal = array[i];
            }
        }

        //2.确定数组的大小
        int rang = maxVal - minVal + 1;
        int[] count = new int[rang];
        //3.再次遍历原来的数组，把原来的数据和计数数组下标对应，然后计数  O(N)
        for (int i = 0; i < array.length; i++) {
            int val = array[i]; // 记录原数组的值
            count[val - minVal]++; // 91 - 91 = 0，开始计数
        }

        //此时，计数数组里面已经存放好了对应关系，遍历计数数组  O(范围+N)
        int index = 0; // 记录重新写回array数组的下标
        for (int i = 0; i < count.length; i++) {
            int val = count[i];
            while(val != 0) {
                array[index++] = i + minVal;
                val--;
            }
        }
    }

    public static void main(String[] args) {
        int[] array = {9,5,6,8,2,4,5,8,7,9,9,6,5,4,1,2,1,5,7,9,0,6,5};
        countSort(array);
        System.out.println(Arrays.toString(array));
    }
}
